자바 알고리즘 라이브러리

자료구조

• Queue -> PriorityQueue
  • add: 데이터 삽입
  • peek: 맨 앞 값 반환
  • poll: 맨 앞 값 반환 후 삭제
• Deque -> LinkedList

시간 복잡도

정렬

• Arrays.sort()
  • 기본형 데이터 타입에서는 듀얼 피봇 퀵소트를 사용한다. 평균 시간 복잡도는 $O(nlogn)$ 이다. 표준 퀵소트보다 더 빠르다.
  • 객체 배열에 대해서는 팀소트 알고리즘이 사용된다. 최악의 경우 시간 복잡도가 $O(nlogn)$ 이다.
• Collections.sort()
  • 내부적으로 Arrays.sort 를 호출하기 때문에 정렬 알고리즘은 Arrays.sort() 와 동일하다.

자료구조

• ArrayList
  • 기본적으로 일정 크기의 배열을 할당하고, 필요에 따라 크기를 재조정 (재할당 및 복사)
  • 접근: $O(1)$
  • 삽입 / 삭제: $O(N)$ 최악의 경우, 리스트의 시작 또는 중간에 삽입 / 삭제 하는 경우
  • 탐색: $O(N)$
• LinkedList
  • 이중 연결 리스트. 양방향 순회 가능
  • 접근: $O(N)$
  • 삽입 / 삭제 : $O(1)$ (노드에 대한 참조가 있을 때)
  • 탐색: $O(N)$
• HashMap
  • 해시 테이블 사용. 해시 테이블을 사용하여 각 키를 배열 인덱스로 매핑하고, 충돌이 발생한 경우 연결 리스트나 트리를 사용하여 충돌 처리
  • 삽입 / 삭제 / 탐색: 평균 $O(1)$, 최악 $O(n)$ (해시 충돌이 많은 경우)
• TreeMap
  • 레드-블랙 트리. 데이터가 항상 정렬된 상태로 유지됨.
  • 삽입 / 삭제 / 탐색: $O(logn)$
• HashSet
  • HashMap 사용. HashSet 내의 각 요소는 HashMap의 키로 저장되고, 모든 값은 동일한 dummy 값이다.
  • 삽입 / 삭제 / 탐색: 평균 $O(1)$, 최악 $O(n)$ (해시 충돌이 많은 경우)
• TreeSet
  • TreeMap 사용. TreeSet 내의 각 요소는 TreeMap 의 키로 저장되고, 값은 사용되지 않는다.
  • 삽입 / 삭제 / 탐색: $O(logn)$
• Stack
  • Vector 클래스를 확장하여 구현된다. Vector 는 동적 배열과 유사하다.
  • 삽입 / 삭제: $O(1)$
  • 탐색 (Top) : $O(1)$
• Queue
  • LinkedList, PriorityQueue 를 사용하여 구현될 수 있다.
  • 삽입: $O(1)$
  • 삭제: $O(1)$ (Linked List 기반일 경우)
  • 탐색: $O(1)$
• Priority Queue
  • 이진 힙을 사용하여 구현된다.
  • 삽입: $O(logn)$
  • 삭제: $O(logn)$ (최소, 최대 요소 삭제)
  • 탐색: $O(1)$ (최소, 최대 요소 탐색)

유용한 메서드

• array to List
  • Arrays.asList(배열)
• List to array
  • 리스트.toArray(할당할 배열)

이진 탐색

• Arrays.binarySearch(배열, 찾으려는 요소, comparator)
  • 찾는 값이 존재하면 인덱스를 반환한다.
  • 찾는 값이 존재하지 않는다면 어디에 위치해야 하는지를 알려주는 값을 음수로 반환한다. => - (원래 위치했어야 하는 인덱스 값) - 1